#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    public:
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            if (!l1 && !l2) return NULL;
            if (!l1) return l2;
            if (!l2) return l1;
            ListNode *rtn = NULL, *list = NULL;                             
            while (l1 && l2) {
                if (l1->val <= l2->val) {
                    if (!rtn) {
                        rtn = l1;
                        list = rtn; 
                    } else {
                        rtn->next = l1;
                        rtn = rtn->next;
                    }
                    l1 = l1->next;     
                } else {
                    if (!rtn) {
                        rtn = l2;
                        list = rtn; 
                    } else {
                        rtn->next = l2;
                        rtn = rtn->next;
                    }
                    l2 = l2->next;     
                } 
            }
            if (l1)
                rtn->next = l1;
            else
                rtn->next = l2;
            return list;
        }
};

//add much better code
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
	ListNode *dummy = new ListNode(0);
	ListNode *cur = dummy;
	while(l1 || l2) {
	    ListNode **merge;
	    if (!l1) merge = &l2;
	    else if (!l2) merge = &l1;
	    else if (l1->val < l2->val) merge = &l1;
	    else merge = &l2;
	    cur->next = *merge;
	    cur = cur->next;
	    *merge = (*merge)->next;
	}
	return dummy->next;
    }

ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList(data, index+1, size);

    return node;
}

//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{

    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
    vector<ListNode *> myList;
    int data[] = {1,4,5,6,7};
    int data2[] = {2,4,5,7,8};
    int data3[] = {2,5,7,8,9};
    ListNode *list1, *list2;
    list1 = newList(data, 0, sizeof(data)/sizeof(int));
    list2 = newList(data2, 0, sizeof(data2)/sizeof(int));
    ListNode *list = mySolution.mergeTwoLists(list1, list2);
    while(list) {
        cout << list->val << " ";
        list= list->next;
    }
    cout << endl;
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
